\subsection{Architecture}

%Tell here about main packages in our system their interaction and
%of course what's the central point in our system (Tagaimpl)

Tagapastry system has been divided into a few packages, each of them grouping
responsibilities of different classes. Central package in our implementation is called
\texttt{dk.itu.samd.group2.tagapastry}. It not only extends required by FreePastry 
\texttt{Application} class but it also exposes
two interfaces namely \texttt{Tagapastry} and \texttt{TagapastryClient} to the future clients 
of our system.
\newline
In the \texttt{Tagapastry} interface we specify which methods must be implemented in our
system i.e. 
\begin{lstlisting}
public void tag(String tag, String tagType, String obj);
public void untag(String tag, String tagType, String obj);
public void search(String tag, String type);
\end{lstlisting}

It is interesting to observer that in mentioned \texttt{search(...)} method 
does not return any value. This
is because this method is responsible only for dispatching initial search request. The data
received as a result of such a request will be delivered to the client implementing \texttt{TagapastryClient}
interface. Below is the definition of mentioned interface:

\begin{lstlisting}
public interface TagapastryClient {
	public void searchResultsDelivery(Tag tag, Vector<IndexEntry> results);
}
\end{lstlisting}

\texttt{MyTagapastryClient} class basically implements just mentioned interface, however,
at that point the most interesting implementation seems to be inside a \texttt{TagapastryImpl}
class. This class is used as a starting point for our client from which all the requests can
be dispatched. Without going first into the details of tag(...), untag(...) and search(...) 
methods let's first have a look at the communication flow between different nodes in the system.

\subsubsection{Communication between nodes}
The communication starts together with the first call to a send(..) method which uses underlying
FreePastry code to route objects of type \texttt{Message} between two nodes. While message is traversing between different nodes towards its destination node, a forward(...) method is called. Finally, once 
a message arrives at a destination a call to the deliver(...) method is issued. The purpose of this 
method is to \textit{execute} just received message. All these methods
are part of the \texttt{TagapastryImpl} class and are never used directly by the client. Instead
they are encapsulated inside methods providing core functionality in our system.

\subsubsection{Types of messages}
In our system we differentiate between many types of messages, however each of them
implements the same \texttt{TagapastryMsg} interface. All of those messages are part of the
\texttt{dk.itu.samd.group2.tagapastry.messages} package and among properties like 
\texttt{type} or \texttt{priority} they also contain \texttt{execute} method with a prototype like below:

\begin{lstlisting}
public void execute(Tagapastry tagimpl) {
// Message specific logic goes here
}

\end{lstlisting}

Indeed, this method (except for situations where we need to buffer the message) is executed first once
a node received that message. This leads to very simple implementation of the \texttt{deliver} method,
in fact, it is independent on a message type.
\\
For each functionality in the system we have created corresponding message type.
\texttt{TagMsg} is responsible for storing data in the system under specified tag.
Objects of type \texttt{UntagMsg} are characterized by providing functionality opposite to the one
available through the objects of \texttt{TagMsg}. Finally \texttt{SearchMsg} contains behavior
responsible for looking up data in the system. Note that according to the prototype of the \texttt{execute(...)} method we always obtain reference to the instance of a Tagapastry class. The argument
for having this instance passed to the message is that, each message may not finish its execution
at \textit{this} node, but instead propagate itself to different node in the network. Indeed, the fact 
that particular message arrived at certain node, does not indicate that we can send confirmation 
to the user that its request has been completed. This situation may happen whenever we need to 
distribute our index among many nodes or whenever we want to look up data in our system. 

\subsection{Index expansion algorithm}

%Try to describe the index distribution from the code point of view
%not on the conceptual level.

Index distribution algorithm is a core part in our design. This algorithm comes 
into play whenever current node's index reaches its expansion threshold. Each node keeps 
its data in memory as a \textit{vector} of \texttt{IndexEntry} objects.
This situation is visualized as on the figure \ref{fig:node_data_rep}.
\begin{figure}
\includegraphics[keepaspectratio=true,width=\linewidth]{graphics/node_data_rep.eps}
\caption{Data representation on a node}
\label{fig:node_data_rep}
\end{figure}

Basically, each entry represents a tagged content, its hash value and a rank. 
Rank property is maintained whenever users tag or untag data in the network. The motivation for \texttt{java.util.Vector<T>} object comes from the distributed nature of the system i.e. we expect many changes to the same data introduced by different users. Vector is responsible for synchronized access
and at the same time provides storage capabilities like a typical \texttt{java.util.ArrayList<T>} class.
Described just vector is part of a container called \texttt{Index} which main responsibility is
to maintain its index entries, but as we will see later also to take care of the buffering of messages.
Each node may be responsible for many indexes, and if any of them exceeds or falls below its limit, 
that index needs to be expanded / retracted (described later) among / from other nodes in the network.
The idea is to expand current content at most between 16 nodes. This number comes from the fact, 
that current content is \textit{expanded} by appending one character to the current objectId from the set, that contains all possible caracteres from the base 16 system. The actual \textit{size} of distribution
is determined by looking at the content stored at current node i.e. if there is no content that
begins with, for example 'C' character then there is no point of appending one to the objectId and
continue on expansion, since there is no data to be sent that starts with mentioned 'C' character.
For all the other characters we basically create corresponding buckets into which we group our
data. Finally for each bucket we create \texttt{IndexExpansionMsg} and route that message
to some \textit{other} node, described at that moment as \texttt{IndexRelative} in the system 
determined by new objectId representation. Since this type of message propagates updates over 
the network, all messages comming to a node currently expanding are buffered by index under 
expansion. This buffer is flushed and messages are processed according to pattern first-in-first-out 
once a node receives \texttt{IndexExpansionConfirmationMsg}.
\newline
At the moment, this is the only implementation for expansion we provide, however, in the future
this solution may be updated by providing third party algorithm. Due to the application of the Strategy
design pattern, the only change that needs to be done requires implementation of the \texttt{DistributionStrategy} interface and injecting that implementation into constructor of the class implementing \texttt{Index} interface, namely \texttt{IndexImpl}.

\subsection{Index retraction algorithm}

This algorithm is similar up to certain degree to the algorithm described above. This time, however,
we deal with a situation where current load on an index is low enough, that it falls below our retraction
limit. For objects very popular on a certain node, this algorithm does not always run - this is because
whenever we untag content on the node we first decrement associated rank property. If rank reaches
value 0, it means that we can remove particular IndexEntry object from the node. It follows
that load on this node has changed. After this operation we need to perform one more step i.e. make 
sure that our data is still correctly sorted by rank, which is done by a Merger class.
More details follow.

\subsubsection{Index retraction maintenance procedure}

Every node is capable of scheduling tasks.
One of the scheduled tasks is to check what is the current load on each node, and if it happens
to be below defined retraction threshold, certain action needs to be taken. Initially, whenever 
a node distributes its content among other nodes, it knows current load of a data on each child to 
which the data has been sent. Over time, knowledge about size of child nodes may become outdated and one of the tasks defined in the maintenance procedure is to discover load changes on a child node and ultimately propagating them to the parent node. How do we get know if the data on a one of the child nodes have changed ?
One idea is to query each node and compare load values, however, its not the best solution since
it involves constant sending of messages to each of the child.
It is not responsibility of the parent to ask each of the child for their storage utilization,
instead it is child's task to notify the parent if such a change has occur. That way we can
save on the total number of messages send in the system. This implementation relies on a \texttt{hasIndexChanged} method that returns true in case of changes, otherwise false.

So, whenever size of a load has changed on a node, a special object
of type \texttt{UpdateSizeMsg} is created and send to a parent together with the value
indicating change - called here \textit{delta}. This is accomplished by following piece of code.
\newline
First, schedule a maintenance procedure
\begin{lstlisting}
this.maintenanceTask = endpoint.scheduleMessage( new MaintenanceMsg(this.getNodeHandle()), 4000, 4000);
\end{lstlisting}

First parameter is a reference to a message that will be executed as a part of this task. The second parameter is a number of miliseconds that should elapse before we start the task for the first time, 
whereas the second parameter indicates time period between subsequent invocations of this task.

Code for handling described tasks - body of the \textit{execute} method in the \texttt{MaintenanceMsg} 
looks like below:
\lstinputlisting{src_examples/maintenance_execute.java}
In lines 2-5 we use instance of \texttt{TagapastryImpl} to obtain a reference to the \texttt{java.util.HashTable<Tag,Index>} object which in turn, stores all the indexes on a particular
node. Lines 6-9 starts iteration over a collection of \texttt{Tag} objects. In lines 10-15 we try
to obtain reference to a particular tag object. Note that this part of code is contained
within try - catch block, that handles exceptions of type \texttt{ConcurrentModificationException}. This
type of exception may be raised by the underlying collection of objects, whenever we try to access
object that has been \textit{just} removed by some \textit{other} update procedure,
for example by index retraction. Once we have obtained reference to a Tag object we retrieve corresponding
index (line 16) and we pass to standard output short information about the tag and the associated
index, in particular its size and delta - indicating change in load. Lines 23-26 provides user with
additional information regarding stored content for that tag. If the current tag is a parent tag
then there is no need to communicate any delta change, since there is no parent for that tag - this
is handled in lines 27-30. If the current node happens to be a child node and there is a change
in a load on that node (line 32) we need to notify its parent. First we obtain a reference
to a parent (lines 33-34), next we build an object of type \texttt{UpdateSizeMsg} and communicate it
to the parent (lines 35-39). The last thing to do is to reset the delta value.

The parent node upon receiving the \texttt{UpdateSizeMsg} proceeds as follows. First it obtains
a reference to a index associated with a tag indicated by the message. After that it runs
\texttt{addToSizeOfSubtree} method with a new size parameter obtained from a child. The body of this
method is shown below:

\begin{lstlisting}
public void addToSizeOfSubtree(int delta) {
	this.sizeOfSubtree += delta;
	if (!this.isRoot()) {
		this.sizeDelta += delta;
	}
	System.out.println("");
	if (this.sizeOfSubtree <= retractionThreshold) {
		this.state = State.RETRACTING;
		RetractionStrategy retStrat = new SimpleRetractionStrategy(this.tagaImpl);
		System.out.println("activation retraction strat");
		retStrat.retract(children);
	}
}
\end{lstlisting}

Upon start execution of this method we always update size of the subtree. Additionally, if
current node is not a root, we also update a delta value (lines 3-5). From the root perspective, it 
does not care about any delta as it does not have to propagate this information any further.
Instead root is interested only in the total size of the subtree. If the size of the subtree,
representing index, falls below certain threshold, we change index state to \textit{RETRACTING}
and we instantiate new object of type \texttt{RetractionStrategy} (line 9). Finally we call
\texttt{retract} method where we pass children of this index (line 11). Body of this method
is defined below:

\lstinputlisting{src_examples/retract_method.java}

Inside this method, for each child sent by a parent we create new message of type
\texttt{IndexRetractionRequestMsg} (lines 2-3) and then depending on a state of the index
(line 5) we either store this message in a buffer (lines 6-8) or we send it to a child node
(lines 9-12).
Child node upon receiving \texttt{IndexRetractionRequestMsg} just removes specified content
from its representation and replies back to its parent with a message of type
\texttt{IndexRetractionResponseMsg}, so it can start processing messages (if any) stored
in a buffer.

\subsection{Buffering of messages and different states}

%Describe buffering (not the existing one but the one after refactorization)
Buffering is a important part of our system, which main purpose is to postpone execution
of messages by some nodes, whenever those nodes are in certain state. A node (referred
below as an instance of IndexRelative class) can change its state whenever it modifies 
content of its own index. In our system we distinguish between state of an index on a node
and an state of the node itself. Depending on these states a process of buffering messages
will be invoked or messages from a buffer will be processed. Below is a short description
of each state for both objects of type Index and objects of type IndexRelative class:
\\
Index
\begin{itemize}
\item RETRACTING Indicates that from this index some entries are being removed and all the
messages sent to this index on a certain node should be postponed.
\item LEAF Indicates whether this index is located on a leaf node (where the actual data is).
\item PARENT Indicates whether this index is located on a parent node.
\end{itemize}

IndexRelative
\begin{itemize}
\item HAVE\_NOT\_ATTEMPTED\_INTERACTION Indicates that to / from this node has not been 
deliver / sent any message.
\item AWAITING\_EXPANSION\_CONFIRMATION It means that to this node has been sent an expansion
message and that we are awaiting for a confirmation from that child.
\item ACTIVE Used when ever child node has replied with confirmation message to its parent node
and means that this child is ready to process messages from a buffer.
\end{itemize}

By default i.e. whenever we instantiate new object of type Index on a node we set its state
to \textit{PARENT}. An assumption is made that new index will have enough space to store given content.
Current state can only change whenever index expansion algorithm needs to be executed. Clearly, this
index will not store any content, as its current data splits between child nodes. Similar, state
of this index can change whenever execution of the index retraction algorithm starts. In this
case index is in state \textit{RETRACTING}.
Once the index expansions / retractions algorithms take into place we also update state of a
IndexRelative object. During expansion process, we create a new objects to which a expansion message
will be sent. Initially we set their state as \textit{HAVE\_NOT\_ATTEMPTED\_INTERACTION}. Together
with the algorithm execution we also update states of nodes so whenever we are \textit{just} about
to send messages to these nodes we update their state to \textit{AWAITING\_EXPANSION\_CONFIRMATION}
which indicates that destination child is busy and stay in that process as long as parent node
does not receive any confirmation, when we can update child state to \texttt{ACTIVE}. A similar
approach is also defined for the index retraction algorithm.
Note that different node's states affect processing of messages sent to that node. An example is
a \texttt{insert(...)} method defined on an index object. Below is an excerpt from that method:

\lstinputlisting{src_examples/indexinsert_method.java}

In the first line we take advantage of the index's state on a node. If it is a parent index (no index
entries) then we obtain a reference to a node and finally depending on its state (lines X-Y) we
either buffer that message or send it directly to a destination node.

\subsection{Looking up of data}

%Describe search procedure and the way we return data to the user
